Lesja kyrkje er ei korskyrkja, med tårnryttar plassert over den kvadratiske korsmidten. Kyrkja er bygd i lafta tømmer, borkledd utvendig, og har om lag 300 sitjeplassar.
Hovudinngangen med våpenhus ligg i venstre korsarmen, og nordre korsarm har ein sideinngang. Koret ligg i austre korsarmen, med eit tilbygd sakristi.
Byggjearbeidet starta opp i 1749, og kyrkja vart vigsla året etter (20. juni 1750). Byggmeister var Ola Fredriksson Hole frå Lesja.
Tidlegare låg kyrkjestaden ca 500 m lenger ned mot elva Lågen, eller ved breidda av Lesjavatnet som vart uttappa på 1800-talet. Den gamle kyrkja var ei stavkyrkje, truleg ombygd til korskyrkje kring midten av 1600-talet. Grunntilhøva var dårlege og staden vindfull, så det vart betemt å byggje ny kyrkje der den står i dag.
I fylgje ei synfaring i 1748 var kyrkja i dårleg forfatning. I 1964 vart det reist ein minnestein på den gamle kyrkjestaden.
Det har vore ein del endringar utvendig gjennom åra, m.a. har hovudinngangen ei tid vore i søre korsarmen. På 1800-talet var det fleire større reparasjonsarbeid, til tider med stor strid om korleis arbeida skulle utførast. Det var til og med foreslått å rive kyrkja og flytte ho eller byggje ny oppe ved hovudvegen gjennom bygda.